ListNode* insertionSortList(ListNode* head) {
        if(!head) return head;
        ListNode *dummy = new ListNode(0);
        dummy->next = head;
        ListNode *cur = head->next, *lastSorted = head;
        
        while(cur)
        {
            if(lastSorted->val <= cur->val)
            {
                lastSorted = lastSorted->next;
            }
            else
            {
                ListNode *pre = dummy;
                while(pre->next->val <= cur->val)
                {
                    pre = pre->next;
                }
                lastSorted->next = cur->next;
                cur->next = pre->next;
                pre->next = cur;
            }
            cur = lastSorted->next;
        }
        return dummy->next;
    }